package com.cat.dynamicPlanning02;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/
 * @create 2025/10/19 19:45
 * @since JDK17
 */

public class Solution26 {
    int n;
    int[] digits;

    int dfs(int offset, int free, int fix) {
        if (offset == 0) {
            return fix;
        }
        int ans = 0, cur = (n / offset) % 10;
        if (fix == 0) {
            ans += dfs(offset / 10, 1, 0);
        }
        if (free == 0) {
            for (int x : digits) {
                if (x < cur) {  // 后面可以随便填了
                    ans += dfs(offset / 10, 1, 1);
                } else if (x == cur) {  // 后面还不能随便填
                    ans += dfs(offset / 10, 0, 1);
                } else {
                    break;
                }
            }
        } else {    // 可以自由选择
            ans += digits.length * dfs(offset / 10, 1, 1);
        }

        return ans;
    }

    public int atMostNGivenDigitSet(String[] nums, int n) {
        int offset = 1, t = n / 10, m = nums.length;
        this.n = n;
        while (t != 0) {
            t /= 10;
            offset *= 10;
        }
        digits = new int[m];
        for (int i = 0; i < m; i++) {
            digits[i] = Integer.valueOf(nums[i]);
        }

        return dfs(offset, 0, 0);
    }
}
